﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution3
{//动态规划加滑动窗口
    public int LengthOfLongestSubstring2(string s)
    {
        int length = s.Length;
        int res = 0;
        for (int i = 0; i < length; i++) { 
        
        int len=GetLen(s, i);
            Console.WriteLine(len);
            res =Math.Max(res, len);
        
        }
        return res;


    }
    //计算当前字符开头的不重复的长度
    private int GetLen(string s, int start)
    {
       
        Dictionary<char,bool> dict = new Dictionary<char,bool>();

        int len = 0;
        for (int i = start; i < s.Length; i++)
        {

            if (dict.ContainsKey(s[i]))
            {
                len=i-start;
                break;

            }
            else { 
            dict.Add(s[i], true);   

            }
        }
        if (len > 0) {
            return len;
        }
        else
        {
            return s.Length-start;
        }

    }
    //优化一下，不要一个一个遍历，遍历过的不要重复加入
    public int LengthOfLongestSubstring(string s)
    {
        Dictionary<char, int> dict = new Dictionary<char, int>();//int是index
        int length = s.Length;
        if (length == 1) {
            return 1;
        }

        int res = 0;
        int start = 0;
        int i = 0;
        while ( i < length)
        {
            int len = 0;
            if (dict.ContainsKey(s[i]))//不是遇到重复的才开始计算长度
            {

                len = i - start;

                Console.WriteLine(s[i]);
                int oldStart = start;
                start = dict[s[i]] + 1;//更新起点，这个起点更新的有点多了
                for (int j = oldStart; j <dict[s[i]]; j++)
                {
                    dict.Remove(s[j]);//移除前面的
                }


                dict[s[i]]=i;//s[i]不变，但是i更新了

            }
            else
            {
                dict.Add(s[i], i);
                len = i - start+1;

            } //先记录一下当前的len
            
            Console.WriteLine(len);
            res = Math.Max(res, len);
            i++;
            

        }
        if (res > 0)
        {
            return res;
        }
        else
        {
            return s.Length - start;//说明没有重复
        }

    }
}
class Program3
{
    static void Main3(string[] args)
    {

        Solution3 solution = new Solution3();
        //string s = "abcabcbb";
        string s = "tmmzuxt";
       int res= solution.LengthOfLongestSubstring(s);
        Console.WriteLine("res"+res);
    }
}
